/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.dex.code;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;

import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecSet;
import com.android.dx.rop.cst.CstString;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Type;
import com.android.dx.util.FixedSizeList;

/**
 * List of local variables. Each local variable entry indicates a range of code
 * which it is valid for, a register number, a name, and a type.
 */
public final class LocalList extends FixedSizeList {

	/** {@code non-null;} empty instance */
	public static final LocalList EMPTY = new LocalList(0);

	/** whether to run the self-check code */
	private static final boolean DEBUG = false;

	/**
	 * Constructs an instance. All indices initially contain {@code null}.
	 * 
	 * @param size
	 *            {@code >= 0;} the size of the list
	 */
	public LocalList(int size) {
		super(size);
	}

	/**
	 * Gets the element at the given index. It is an error to call this with the
	 * index for an element which was never set; if you do that, this will throw
	 * {@code NullPointerException}.
	 * 
	 * @param n
	 *            {@code >= 0, < size();} which index
	 * @return {@code non-null;} element at that index
	 */
	public Entry get(int n) {
		return (Entry) get0(n);
	}

	/**
	 * Sets the entry at the given index.
	 * 
	 * @param n
	 *            {@code >= 0, < size();} which index
	 * @param entry
	 *            {@code non-null;} the entry to set at {@code n}
	 */
	public void set(int n, Entry entry) {
		set0(n, entry);
	}

	/**
	 * Does a human-friendly dump of this instance.
	 * 
	 * @param out
	 *            {@code non-null;} where to dump
	 * @param prefix
	 *            {@code non-null;} prefix to attach to each line of output
	 */
	public void debugPrint(PrintStream out, String prefix) {
		int sz = size();

		for (int i = 0; i < sz; i++) {
			out.print(prefix);
			out.println(get(i));
		}
	}

	/**
	 * Disposition of a local entry.
	 */
	public static enum Disposition {
		/** local started (introduced) */
		START,

		/** local ended without being replaced */
		END_SIMPLY,

		/** local ended because it was directly replaced */
		END_REPLACED,

		/** local ended because it was moved to a different register */
		END_MOVED,

		/**
		 * local ended because the previous local clobbered this one (because it
		 * is category-2)
		 */
		END_CLOBBERED_BY_PREV,

		/**
		 * local ended because the next local clobbered this one (because this
		 * one is a category-2)
		 */
		END_CLOBBERED_BY_NEXT;
	}

	/**
	 * Entry in a local list.
	 */
	public static class Entry implements Comparable<Entry> {

		/** {@code >= 0;} address */
		private final int address;

		/** {@code non-null;} disposition of the local */
		private final Disposition disposition;

		/** {@code non-null;} register spec representing the variable */
		private final RegisterSpec spec;

		/** {@code non-null;} variable type (derived from {@code spec}) */
		private final CstType type;

		/**
		 * Constructs an instance.
		 * 
		 * @param address
		 *            {@code >= 0;} address
		 * @param disposition
		 *            {@code non-null;} disposition of the local
		 * @param spec
		 *            {@code non-null;} register spec representing the variable
		 */
		public Entry(int address, Disposition disposition, RegisterSpec spec) {
			if (address < 0) {
				throw new IllegalArgumentException("address < 0");
			}

			if (disposition == null) {
				throw new NullPointerException("disposition == null");
			}

			try {
				if (spec.getLocalItem() == null) {
					throw new NullPointerException(
							"spec.getLocalItem() == null");
				}
			} catch (NullPointerException ex) {
				// Elucidate the exception.
				throw new NullPointerException("spec == null");
			}

			this.address = address;
			this.disposition = disposition;
			this.spec = spec;
			this.type = CstType.intern(spec.getType());
		}

		/** {@inheritDoc} */
		public String toString() {
			return Integer.toHexString(address) + " " + disposition + " "
					+ spec;
		}

		/** {@inheritDoc} */
		public boolean equals(Object other) {
			if (!(other instanceof Entry)) {
				return false;
			}

			return (compareTo((Entry) other) == 0);
		}

		/**
		 * Compares by (in priority order) address, end then start disposition
		 * (variants of end are all consistered equivalent), and spec.
		 * 
		 * @param other
		 *            {@code non-null;} entry to compare to
		 * @return {@code -1..1;} standard result of comparison
		 */
		public int compareTo(Entry other) {
			if (address < other.address) {
				return -1;
			} else if (address > other.address) {
				return 1;
			}

			boolean thisIsStart = isStart();
			boolean otherIsStart = other.isStart();

			if (thisIsStart != otherIsStart) {
				return thisIsStart ? 1 : -1;
			}

			return spec.compareTo(other.spec);
		}

		/**
		 * Gets the address.
		 * 
		 * @return {@code >= 0;} the address
		 */
		public int getAddress() {
			return address;
		}

		/**
		 * Gets the disposition.
		 * 
		 * @return {@code non-null;} the disposition
		 */
		public Disposition getDisposition() {
			return disposition;
		}

		/**
		 * Gets whether this is a local start. This is just shorthand for
		 * {@code getDisposition() == Disposition.START}.
		 * 
		 * @return {@code true} iff this is a start
		 */
		public boolean isStart() {
			return disposition == Disposition.START;
		}

		/**
		 * Gets the variable name.
		 * 
		 * @return {@code null-ok;} the variable name
		 */
		public CstString getName() {
			return spec.getLocalItem().getName();
		}

		/**
		 * Gets the variable signature.
		 * 
		 * @return {@code null-ok;} the variable signature
		 */
		public CstString getSignature() {
			return spec.getLocalItem().getSignature();
		}

		/**
		 * Gets the variable's type.
		 * 
		 * @return {@code non-null;} the type
		 */
		public CstType getType() {
			return type;
		}

		/**
		 * Gets the number of the register holding the variable.
		 * 
		 * @return {@code >= 0;} the number of the register holding the variable
		 */
		public int getRegister() {
			return spec.getReg();
		}

		/**
		 * Gets the RegisterSpec of the register holding the variable.
		 * 
		 * @return {@code non-null;} RegisterSpec of the holding register.
		 */
		public RegisterSpec getRegisterSpec() {
			return spec;
		}

		/**
		 * Returns whether or not this instance matches the given spec.
		 * 
		 * @param otherSpec
		 *            {@code non-null;} the spec in question
		 * @return {@code true} iff this instance matches {@code spec}
		 */
		public boolean matches(RegisterSpec otherSpec) {
			return spec.equalsUsingSimpleType(otherSpec);
		}

		/**
		 * Returns whether or not this instance matches the spec in the given
		 * instance.
		 * 
		 * @param other
		 *            {@code non-null;} another entry
		 * @return {@code true} iff this instance's spec matches {@code other}
		 */
		public boolean matches(Entry other) {
			return matches(other.spec);
		}

		/**
		 * Returns an instance just like this one but with the disposition set
		 * as given.
		 * 
		 * @param disposition
		 *            {@code non-null;} the new disposition
		 * @return {@code non-null;} an appropriately-constructed instance
		 */
		public Entry withDisposition(Disposition disposition) {
			if (disposition == this.disposition) {
				return this;
			}

			return new Entry(address, disposition, spec);
		}
	}

	/**
	 * Constructs an instance for the given method, based on the given block
	 * order and intermediate local information.
	 * 
	 * @param insns
	 *            {@code non-null;} instructions to convert
	 * @return {@code non-null;} the constructed list
	 */
	public static LocalList make(DalvInsnList insns) {
		int sz = insns.size();

		/*
		 * Go through the insn list, looking for all the local variable
		 * pseudoinstructions, splitting out LocalSnapshots into separate
		 * per-variable starts, adding explicit ends wherever a variable is
		 * replaced or moved, and collecting these and all the other local
		 * variable "activity" together into an output list (without the other
		 * insns).
		 * 
		 * Note: As of this writing, this method won't be handed any insn lists
		 * that contain local ends, but I (danfuzz) expect that to change at
		 * some point, when we start feeding that info explicitly into the rop
		 * layer rather than only trying to infer it. So, given that
		 * expectation, this code is written to deal with them.
		 */

		MakeState state = new MakeState(sz);

		for (int i = 0; i < sz; i++) {
			DalvInsn insn = insns.get(i);

			if (insn instanceof LocalSnapshot) {
				RegisterSpecSet snapshot = ((LocalSnapshot) insn).getLocals();
				state.snapshot(insn.getAddress(), snapshot);
			} else if (insn instanceof LocalStart) {
				RegisterSpec local = ((LocalStart) insn).getLocal();
				state.startLocal(insn.getAddress(), local);
			} else if (insn instanceof LocalEnd) {
				RegisterSpec local = ((LocalEnd) insn).getLocal();
				state.endLocal(insn.getAddress(), local);
			}
		}

		LocalList result = state.finish();

		if (DEBUG) {
			debugVerify(result);
		}

		return result;
	}

	/**
	 * Debugging helper that verifies the constraint that a list doesn't contain
	 * any redundant local starts and that local ends that are due to
	 * replacements are properly annotated.
	 */
	private static void debugVerify(LocalList locals) {
		try {
			debugVerify0(locals);
		} catch (RuntimeException ex) {
			int sz = locals.size();
			for (int i = 0; i < sz; i++) {
				System.err.println(locals.get(i));
			}
			throw ex;
		}

	}

	/**
	 * Helper for {@link #debugVerify} which does most of the work.
	 */
	private static void debugVerify0(LocalList locals) {
		int sz = locals.size();
		Entry[] active = new Entry[65536];

		for (int i = 0; i < sz; i++) {
			Entry e = locals.get(i);
			int reg = e.getRegister();

			if (e.isStart()) {
				Entry already = active[reg];

				if ((already != null) && e.matches(already)) {
					throw new RuntimeException("redundant start at "
							+ Integer.toHexString(e.getAddress()) + ": got "
							+ e + "; had " + already);
				}

				active[reg] = e;
			} else {
				if (active[reg] == null) {
					throw new RuntimeException("redundant end at "
							+ Integer.toHexString(e.getAddress()));
				}

				int addr = e.getAddress();
				boolean foundStart = false;

				for (int j = i + 1; j < sz; j++) {
					Entry test = locals.get(j);
					if (test.getAddress() != addr) {
						break;
					}
					if (test.getRegisterSpec().getReg() == reg) {
						if (test.isStart()) {
							if (e.getDisposition() != Disposition.END_REPLACED) {
								throw new RuntimeException(
										"improperly marked end at "
												+ Integer.toHexString(addr));
							}
							foundStart = true;
						} else {
							throw new RuntimeException("redundant end at "
									+ Integer.toHexString(addr));
						}
					}
				}

				if (!foundStart
						&& (e.getDisposition() == Disposition.END_REPLACED)) {
					throw new RuntimeException(
							"improper end replacement claim at "
									+ Integer.toHexString(addr));
				}

				active[reg] = null;
			}
		}
	}

	/**
	 * Intermediate state when constructing a local list.
	 */
	public static class MakeState {

		/** {@code non-null;} result being collected */
		private final ArrayList<Entry> result;

		/**
		 * {@code >= 0;} running count of nulled result entries, to help with
		 * sizing the final list
		 */
		private int nullResultCount;

		/** {@code null-ok;} current register mappings */
		private RegisterSpecSet regs;

		/** {@code null-ok;} result indices where local ends are stored */
		private int[] endIndices;

		/** {@code >= 0;} last address seen */
		private int lastAddress;

		/**
		 * Constructs an instance.
		 */
		public MakeState(int initialSize) {
			result = new ArrayList<Entry>(initialSize);
			nullResultCount = 0;
			regs = null;
			endIndices = null;
			lastAddress = 0;
		}

		/**
		 * Checks the address and other vitals as a prerequisite to further
		 * processing.
		 * 
		 * @param address
		 *            {@code >= 0;} address about to be processed
		 * @param reg
		 *            {@code >= 0;} register number about to be processed
		 */
		private void aboutToProcess(int address, int reg) {
			boolean first = (endIndices == null);

			if ((address == lastAddress) && !first) {
				return;
			}

			if (address < lastAddress) {
				throw new RuntimeException("shouldn't happen");
			}

			if (first || (reg >= endIndices.length)) {
				/*
				 * This is the first allocation of the state set and index
				 * array, or we need to grow. (The latter doesn't happen much;
				 * in fact, we have only ever observed it happening in test
				 * cases, never in "real" code.)
				 */
				int newSz = reg + 1;
				RegisterSpecSet newRegs = new RegisterSpecSet(newSz);
				int[] newEnds = new int[newSz];
				Arrays.fill(newEnds, -1);

				if (!first) {
					newRegs.putAll(regs);
					System.arraycopy(endIndices, 0, newEnds, 0,
							endIndices.length);
				}

				regs = newRegs;
				endIndices = newEnds;
			}
		}

		/**
		 * Sets the local state at the given address to the given snapshot. The
		 * first call on this instance must be to this method, so that the
		 * register state can be properly sized.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param specs
		 *            {@code non-null;} spec set representing the locals
		 */
		public void snapshot(int address, RegisterSpecSet specs) {
			if (DEBUG) {
				System.err.printf("%04x snapshot %s\n", address, specs);
			}

			int sz = specs.getMaxSize();
			aboutToProcess(address, sz - 1);

			for (int i = 0; i < sz; i++) {
				RegisterSpec oldSpec = regs.get(i);
				RegisterSpec newSpec = filterSpec(specs.get(i));

				if (oldSpec == null) {
					if (newSpec != null) {
						startLocal(address, newSpec);
					}
				} else if (newSpec == null) {
					endLocal(address, oldSpec);
				} else if (!newSpec.equalsUsingSimpleType(oldSpec)) {
					endLocal(address, oldSpec);
					startLocal(address, newSpec);
				}
			}

			if (DEBUG) {
				System.err.printf("%04x snapshot done\n", address);
			}
		}

		/**
		 * Starts a local at the given address.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param startedLocal
		 *            {@code non-null;} spec representing the started local
		 */
		public void startLocal(int address, RegisterSpec startedLocal) {
			if (DEBUG) {
				System.err.printf("%04x start %s\n", address, startedLocal);
			}

			int regNum = startedLocal.getReg();

			startedLocal = filterSpec(startedLocal);
			aboutToProcess(address, regNum);

			RegisterSpec existingLocal = regs.get(regNum);

			if (startedLocal.equalsUsingSimpleType(existingLocal)) {
				// Silently ignore a redundant start.
				return;
			}

			RegisterSpec movedLocal = regs.findMatchingLocal(startedLocal);
			if (movedLocal != null) {
				/*
				 * The same variable was moved from one register to another. So
				 * add an end for its old location.
				 */
				addOrUpdateEnd(address, Disposition.END_MOVED, movedLocal);
			}

			int endAt = endIndices[regNum];

			if (existingLocal != null) {
				/*
				 * There is an existing (but non-matching) local. Add an
				 * explicit end for it.
				 */
				add(address, Disposition.END_REPLACED, existingLocal);
			} else if (endAt >= 0) {
				/*
				 * Look for an end local for the same register at the same
				 * address. If found, then update it or delete it, depending on
				 * whether or not it represents the same variable as the one
				 * being started.
				 */
				Entry endEntry = result.get(endAt);
				if (endEntry.getAddress() == address) {
					if (endEntry.matches(startedLocal)) {
						/*
						 * There was already an end local for the same variable
						 * at the same address. This turns out to be
						 * superfluous, as we are starting up the exact same
						 * local. This situation can happen when a single local
						 * variable got somehow "split up" during intermediate
						 * processing. In any case, rather than represent the
						 * end-then-start, just remove the old end.
						 */
						result.set(endAt, null);
						nullResultCount++;
						regs.put(startedLocal);
						endIndices[regNum] = -1;
						return;
					} else {
						/*
						 * There was a different variable ended at the same
						 * address. Update it to indicate that it was ended due
						 * to a replacement (rather than ending for no
						 * particular reason).
						 */
						endEntry = endEntry
								.withDisposition(Disposition.END_REPLACED);
						result.set(endAt, endEntry);
					}
				}
			}

			/*
			 * The code above didn't find and remove an unnecessary local end,
			 * so we now have to add one or more entries to the output to
			 * capture the transition.
			 */

			/*
			 * If the local just below (in the register set at reg-1) is of
			 * category-2, then it is ended by this new start.
			 */
			if (regNum > 0) {
				RegisterSpec justBelow = regs.get(regNum - 1);
				if ((justBelow != null) && justBelow.isCategory2()) {
					addOrUpdateEnd(address, Disposition.END_CLOBBERED_BY_NEXT,
							justBelow);
				}
			}

			/*
			 * Similarly, if this local is category-2, then the local just above
			 * (if any) is ended by the start now being emitted.
			 */
			if (startedLocal.isCategory2()) {
				RegisterSpec justAbove = regs.get(regNum + 1);
				if (justAbove != null) {
					addOrUpdateEnd(address, Disposition.END_CLOBBERED_BY_PREV,
							justAbove);
				}
			}

			/*
			 * TODO: Add an end for the same local in a different reg, if any
			 * (that is, if the local migrates from vX to vY, we should note
			 * that as a local end in vX).
			 */

			add(address, Disposition.START, startedLocal);
		}

		/**
		 * Ends a local at the given address, using the disposition
		 * {@code END_SIMPLY}.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param endedLocal
		 *            {@code non-null;} spec representing the local being ended
		 */
		public void endLocal(int address, RegisterSpec endedLocal) {
			endLocal(address, endedLocal, Disposition.END_SIMPLY);
		}

		/**
		 * Ends a local at the given address.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param endedLocal
		 *            {@code non-null;} spec representing the local being ended
		 * @param disposition
		 *            reason for the end
		 */
		public void endLocal(int address, RegisterSpec endedLocal,
				Disposition disposition) {
			if (DEBUG) {
				System.err.printf("%04x end %s\n", address, endedLocal);
			}

			int regNum = endedLocal.getReg();

			endedLocal = filterSpec(endedLocal);
			aboutToProcess(address, regNum);

			int endAt = endIndices[regNum];

			if (endAt >= 0) {
				/*
				 * The local in the given register is already ended. Silently
				 * return without adding anything to the result.
				 */
				return;
			}

			// Check for start and end at the same address.
			if (checkForEmptyRange(address, endedLocal)) {
				return;
			}

			add(address, disposition, endedLocal);
		}

		/**
		 * Helper for {@link #endLocal}, which handles the cases where and end
		 * local is issued at the same address as a start local for the same
		 * register. If this case is found, then this method will remove the
		 * start (as the local was never actually active), update the
		 * {@link #endIndices} to be accurate, and if needed update the
		 * newly-active end to reflect an altered disposition.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param endedLocal
		 *            {@code non-null;} spec representing the local being ended
		 * @return {@code true} iff this method found the case in question and
		 *         adjusted things accordingly
		 */
		private boolean checkForEmptyRange(int address, RegisterSpec endedLocal) {
			int at = result.size() - 1;
			Entry entry;

			// Look for a previous entry at the same address.
			for (/* at */; at >= 0; at--) {
				entry = result.get(at);

				if (entry == null) {
					continue;
				}

				if (entry.getAddress() != address) {
					// We didn't find any match at the same address.
					return false;
				}

				if (entry.matches(endedLocal)) {
					break;
				}
			}

			/*
			 * In fact, we found that the endedLocal had started at the same
			 * address, so do all the requisite cleanup.
			 */

			regs.remove(endedLocal);
			result.set(at, null);
			nullResultCount++;

			int regNum = endedLocal.getReg();
			boolean found = false;
			entry = null;

			// Now look back further to update where the register ended.
			for (at--; at >= 0; at--) {
				entry = result.get(at);

				if (entry == null) {
					continue;
				}

				if (entry.getRegisterSpec().getReg() == regNum) {
					found = true;
					break;
				}
			}

			if (found) {
				// We found an end for the same register.
				endIndices[regNum] = at;

				if (entry.getAddress() == address) {
					/*
					 * It's still the same address, so update the disposition.
					 */
					result.set(at,
							entry.withDisposition(Disposition.END_SIMPLY));
				}
			}

			return true;
		}

		/**
		 * Converts a given spec into the form acceptable for use in a local
		 * list. This, in particular, transforms the "known null" type into
		 * simply {@code Object}. This method needs to be called for any spec
		 * that is on its way into a locals list.
		 * <p>
		 * This isn't necessarily the cleanest way to achieve the goal of not
		 * representing known nulls in a locals list, but it gets the job done.
		 * </p>
		 * 
		 * @param orig
		 *            {@code null-ok;} the original spec
		 * @return {@code null-ok;} an appropriately modified spec, or the
		 *         original if nothing needs to be done
		 */
		private static RegisterSpec filterSpec(RegisterSpec orig) {
			if ((orig != null) && (orig.getType() == Type.KNOWN_NULL)) {
				return orig.withType(Type.OBJECT);
			}

			return orig;
		}

		/**
		 * Adds an entry to the result, updating the adjunct tables accordingly.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param disposition
		 *            {@code non-null;} the disposition
		 * @param spec
		 *            {@code non-null;} spec representing the local
		 */
		private void add(int address, Disposition disposition, RegisterSpec spec) {
			int regNum = spec.getReg();

			result.add(new Entry(address, disposition, spec));

			if (disposition == Disposition.START) {
				regs.put(spec);
				endIndices[regNum] = -1;
			} else {
				regs.remove(spec);
				endIndices[regNum] = result.size() - 1;
			}
		}

		/**
		 * Adds or updates an end local (changing its disposition). If this
		 * would cause an empty range for a local, this instead removes the
		 * local entirely.
		 * 
		 * @param address
		 *            {@code >= 0;} the address
		 * @param disposition
		 *            {@code non-null;} the disposition
		 * @param spec
		 *            {@code non-null;} spec representing the local
		 */
		private void addOrUpdateEnd(int address, Disposition disposition,
				RegisterSpec spec) {
			if (disposition == Disposition.START) {
				throw new RuntimeException("shouldn't happen");
			}

			int regNum = spec.getReg();
			int endAt = endIndices[regNum];

			if (endAt >= 0) {
				// There is a previous end.
				Entry endEntry = result.get(endAt);
				if ((endEntry.getAddress() == address)
						&& endEntry.getRegisterSpec().equals(spec)) {
					/*
					 * The end is for the right address and variable, so update
					 * it.
					 */
					result.set(endAt, endEntry.withDisposition(disposition));
					regs.remove(spec); // TODO: Is this line superfluous?
					return;
				}
			}

			endLocal(address, spec, disposition);
		}

		/**
		 * Finishes processing altogether and gets the result.
		 * 
		 * @return {@code non-null;} the result list
		 */
		public LocalList finish() {
			aboutToProcess(Integer.MAX_VALUE, 0);

			int resultSz = result.size();
			int finalSz = resultSz - nullResultCount;

			if (finalSz == 0) {
				return EMPTY;
			}

			/*
			 * Collect an array of only the non-null entries, and then sort it
			 * to get a consistent order for everything: Local ends and starts
			 * for a given address could come in any order, but we want ends
			 * before starts as well as registers in order (within ends or
			 * starts).
			 */

			Entry[] resultArr = new Entry[finalSz];

			if (resultSz == finalSz) {
				result.toArray(resultArr);
			} else {
				int at = 0;
				for (Entry e : result) {
					if (e != null) {
						resultArr[at++] = e;
					}
				}
			}

			Arrays.sort(resultArr);

			LocalList resultList = new LocalList(finalSz);

			for (int i = 0; i < finalSz; i++) {
				resultList.set(i, resultArr[i]);
			}

			resultList.setImmutable();
			return resultList;
		}
	}
}
